/*
 * @lc app=leetcode.cn id=581 lang=typescript
 *
 * [581] 最短无序连续子数组
 */

// @lc code=start
function findUnsortedSubarray(nums: number[]): number {
  const stack = [];
  const m = nums.length;
  let left = Number.POSITIVE_INFINITY;
  let right = Number.NEGATIVE_INFINITY;

  // 单调递增栈，找left
  for (let i = 0; i < m; i++) {
    while (stack.length && nums[i] < nums[stack[stack.length - 1]]) {
      left = Math.min(left, stack.pop());
    }
    stack.push(i);
  }
  stack.length = 0;
  // 单调递减栈，找right
  for (let i = m - 1; i >= 0; i--) {
    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
      right = Math.max(right, stack.pop());
    }
    stack.push(i);
  }

  return isFinite(left) ? right - left + 1 : 0;
}
// @lc code=end
